/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/kth-prime-number
   @Language: C++
   @Datetime: 19-04-27 09:55
   */

class Solution {
public:
	/**
	 * @param n: the prime number
	 * @return: the rank of the number
	 */
	int kthPrime(int n) {
		// write your code here
		vector<bool> primes(n+1,true);
		primes[0]=primes[1]=false;
		for(int i=2; i<=n; ++i){
			if(!primes[i]) continue;
			for(int j=i+i; j<=n; j+=i)
				primes[j]=false;
		}
		int k=0;
		for(int i=0; i<=n; ++i)
			if(primes[i]) ++k;
		return k;
	}
};
